package com.note.feng.leetcode.algorithms.easy.five;

import java.util.*;
import java.util.stream.Collectors;

public class FiveHundredNinetyFour {

    /**
     * 594 最长和谐子序列
     * 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
     *
     * 现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
     *
     * 数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
     *
     * 示例 1：
     *
     * 输入：nums = [1,3,2,2,5,2,3,7]
     * 输出：5
     * 解释：最长的和谐子序列是 [3,2,2,2,3]
     * 示例 2：
     *
     * 输入：nums = [1,2,3,4]
     * 输出：2
     * 示例 3：
     *
     * 输入：nums = [1,1,1,1]
     * 输出：0
     *
     * 提示：
     *
     * 1 <= nums.length <= 2 * 104
     * -109 <= nums[i] <= 109
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/longest-harmonious-subsequence
     */
    /**
     * 解法：哈希
     * 最长和谐子序列，可以理解为：数组中，两个差为1的元素的个数总和最大的一组
     * map 存储元素和元素出现的次数，再遍历找到两个差为1的元素的个数总和最大的组合
     *
     * 方法的优化：
     * 不需要 list ，只需要遍历 map 即可，判断是否存在当前 key + 1 的key，
     * 若存在，计算两个元素的个数和，并赋值给 max 当前的最大值
     * @param nums
     * @return
     */
    public int findLHS(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for (int num : nums){
            if(map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else{
                map.put(num, 1);
                list.add(num);
            }
        }
        list = list.stream().sorted(Comparator.comparing(Integer::intValue)).collect(Collectors.toList());
        int max = 0;
        for (int i = 1; i < list.size(); i++) {
            int l = list.get(i - 1);
            int r = list.get(i);
            if(r - l == 1){
                int sum = map.get(l) + map.get(r);
                max = Math.max(max, sum);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int [] nums = new int[]{1,3,2,2,5,2,3,7};
        FiveHundredNinetyFour f = new FiveHundredNinetyFour();
        f.findLHS(nums);
    }
}
